package junior.DynamicProgramming动态规划;

public class 最大公共子串 {
    static Character[] str1 = {'B','A','C','D','B'};
    static Character[] str2 = {'B','E','C','B'};
    static int len1 = str1.length+1;
    static int len2 = str2.length+1;
    static int[][]dp = new int[len1][len2];
    public static void main(String[] args) {
        System.out.println(fun(str1.length - 1, str2.length - 1));
    }

    /**
     * 递归法求最长公共子串
     * @param str1_len
     * @param str2_len
     * @return
     */
    public static String fun(int str1_len,int str2_len){
        if (str1_len == -1 || str2_len == -1) {
            return "";
        }
        if(str1[str1_len] == str2[str2_len]){
            return fun(str1_len-1,str2_len-1)+str1[str1_len];
        }else {
            String s1 = fun(str1_len-1,str2_len);
            String s2 = fun(str1_len,str2_len-1);
            return s1.length() >= s2.length() ? s1 : s2;
        }
    }

    public static String fun1(int str1_len,int str2_len){
        if (str1_len == -1 || str2_len == -1) {
            return "";
        }
        if(str1[str1_len] == str2[str2_len]){
            return fun(str1_len-1,str2_len-1)+str1[str1_len];
        }else {
            String s1 = fun(str1_len-1,str2_len);
            String s2 = fun(str1_len,str2_len-1);
            return s1.length() > s2.length() ? s1 : s2;
        }
    }
}
